
//1765.地图中的最高点
class Solution {
public:
    vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {
        int n=isWater.size(),m=isWater[0].size();
        int dx[]={0,0,-1,1};
        int dy[]={1,-1,0,0};

        //相邻格子的高度差至多为1,已知水域的高度为0,那不就可以从水域开始向外进行扩展
        queue<pair<int,int>> q;
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<m;j++)
            {
                if(isWater[i][j]==1)
                {
                    isWater[i][j]=-1;   //先将水面置为-1,如果直接将其置为0,就和陆地搞混在一起了
                    q.push({i,j});
                }
            }
        }   

        int step=0;
        while(!q.empty())
        {
            int _size=q.size();
            step++;
            for(int i=0;i<_size;i++)
            {
                int x=q.front().first,y=q.front().second;
                q.pop();
                for(int k=0;k<4;k++)
                {
                    int a=x+dx[k],b=y+dy[k];
                    if(a>=0&&a<n&&b>=0&&b<m&&!isWater[a][b])
                    {
                        isWater[a][b]=step;   //对陆地的高度进行更新,只能更新依次,报站高度差不超过1
                        q.push({a,b});
                    }
                }
            }
        }    
        for(int i=0;i<n;i++)
        for(int j=0;j<m;j++)
        if(isWater[i][j]==-1) isWater[i][j]=0;  //将用-1标记的水面全部置为0
        return isWater;
    }
};